An attribute-based AC (ABAC) policy defines access control permissions based on the attributes of the subject, of the resource, and of the action that the subject is to perform on the resource (e.g., read, write). When the policy is enforced in a computer system or computer network, it controls access to entities in the system or network and thereby influences their state of operation. A resource may be, inter alia, a portion of a personal storage quota, a business unit storage quota, an information retrieval system, a (portion of a) database, an online service, a protected webpage or a physical device.
Functional expressions, in particular rules, in an ABAC policy may be nested hierarchically in a conditional fashion, so that attribute values will influence what further rules are to be applied. To this end, an expression in a policy may evaluate not only to Permit and Deny, but also to Not applicable or a value equivalent to this. An expression may also evaluate to intermediate attribute values, bags of attribute values or assume an error state. In particular the expression may be divided into a target portion, which may trigger a Not applicable state, and a condition portion. Any conflicts arising in the decision making may be settled by way of appropriate combining algorithms, such as permit-overrides and deny-overrides. The final decision for an access control request is the result of a specifically identified top level object. Based on a policy or policy set (unless otherwise indicated, these terms are used interchangeably herein) that covers a broad range of resources and subjects and a given request, it is often possible to obtain a decision by evaluating only a fraction of all functional expressions in the policy. Conversely, it cannot always be ascertained prima facie whether a request contains enough attribute values to allow a successful policy evaluation.
To illustrate, a simple enterprise policy governs use of company printers and company documents (resources). For printers, the printer location is a remote attribute available in a directory. For documents, document classification, type, stage and author are remote attributes available in a database. For users (subjects), their clearance, office location, and nationality are remote attributes available in a directory. The policy (cf. FIG. 2) grants a user access to printers if his or her office is in the same location as the printer. For documents, access is allowed if the user has the same or higher clearance as the document classification, except for document on the “draft” stage, which may be accessed by the author only. Furthermore, if the document type is “military”, then only users of domestic nationality may see the document.
There currently exist general-purpose AC languages that have the richness to express fine-grained conditions and conditions which depend on external data. One particular example of an AC language is the eXtensible Access Control Markup Language (XACML) which is the subject of standardization work in a Technical Committee within the Organization for the Advancement of Structured Information Standards (OASIS, 35 Corporate Drive Suite 150, Burlington, MA). A policy encoded with XACML consists of functional expressions in attribute values, and the return value (decision) of the policy is one of Permit, Deny, Not Applicable, or Indeterminate. An XACML policy can apply to many different situations, that is, different subjects, resources, actions and environments and may give different results for different combinations of these. The XACML specification defines how a policy is evaluated for a request (or access request), particularly what policy attributes are to be evaluated or, at least, which values are required to exist for a successful evaluation to result. Key characteristics of this evaluation process are that the access request (the query against the policy) must describe the attempted access to a protected resource fully. In practice, it may be that the request is constructed in multiple stages by different components, so that a PEP (Policy Enforcement Point) provides only some initial attribute values and a PDP (Policy Decision Point) or other components can dynamically fetch more attribute values from remote sources as they are needed.
In many situations, it is desirable to automatically derive from an XACML policy a subset which applies to a restricted situation, such as the policy which applies to a specified individual subject or resource, a type of subject or resource, a special action, a certain access location, and so on. The Master's thesis J. Sandberg, “Administrative queries in XACML—feasibility of partial-query evaluation”, Department of Computer and Systems Sciences at Stockholm University and School of Computer Science and Communication, Royal Institute of Technology, Stockholm (2006), which is hereby included by reference, describes evaluation of so-called administrative queries (e.g., “What can user X do?”) to a policy by an approach involving partial evaluation of the policy. Such partial evaluation is based on a partial request in which some attributes have been assigned values and some have been left undefined and yields as output a simplified policy, which is represented in the same form as the original policy but typically evaluates faster since it is expressed as a smaller amount of code and/or contains fewer variable attributes. It is expected that the simplified policy and the original policy provide identical access decision in response to identical requests, provided these requests do not contradict the partial request forming the basis for the partial evaluation.
In section 3.2 of Sandberg's thesis, several simplification rules are derived, including rules governing allowed simplifications of expressions (e.g., rules, policies and policy sets) joined by different combining algorithms, such as deny-overrides and permit-overrides. Examples of these simplification rules include:                1. Any expression evaluating to Not applicable is removed.        2. For expressions appearing under a deny-overrides rule combining algorithm:                    2.1. If there exists an expression that evaluates to Deny whose target is applicable, remove all other rules and return Deny.            2.2. If there exists an expression that evaluates to Indeterminate whose target is applicable, remove any rule with a Permit effect.            2.3. If there exists an expression that evaluates to Permit whose target is applicable, remove all expressions that evaluate to Indeterminate if their effect is Permit.            2.4. If there exist no expressions with a Deny effect and at least one expression with a Permit effect, remove all other expressions and return Permit.            2.5. If there exist no expressions with a Deny effect and all rules evaluate to Indeterminate, return Indeterminate.                        3. For expressions appearing under a permit-overrides policy combining algorithm:                    3.1. If there is an expression evaluating to Permit whose target is applicable, remove all other expressions and return Permit.            3.2. If there is an expression evaluated to Deny whose target is applicable, remove all expressions which have returned Indeterminate.                        
This approach is useful in the context of evaluating administrative queries, wherein it is feasible to verify that the requests to the simplified policy are consistent, i.e., do not contradict, the partial request forming the basis for the partial evaluation. It would be desirable, however, to broaden the applicability of the partial evaluation technique in the field of ABAC policies.